/*
 * Amos Kittelson 
 * COP3503 - Computer Science 2
 * Assignment 3 - Railroad Building
 * Due 6 July 2010 (Extended due to military duty)
 */

public class Heap {
	
	// TODO: Figure out how to make Comparable not so Generic
	// Can we pass a type with the constructor?

	// Array to store all the elements in it
	// e[1] is the minimum value in the heap
	private Comparable[] e;

	// Keeps track of the size of the heap
	private int size;
	
	// all elements start a one
	final int OFFSET = 1;
	
	Boolean debug = false;
	
	// Constructor for an empty heap
	public Heap(){
		e = new Comparable[100];
		size = 0;
	}
	
	// Constructor for a heap of x size
	public Heap(int sz){
		size = sz;
		e = new Comparable[(size + OFFSET) * 2];
		
		// for (i = 0; i < size + OFFSET; i++)
		//	e[i] = new Edge();
			
		
	}
	
	// Constructor for an incoming array
	public Heap(Graph eIn){
		
		
		// Create the new array for the heap
		size = eIn.sizeOf();
		e = new Comparable[(size + OFFSET) * 2];
		
		if (debug) prt("Creating array of size " + (size + OFFSET) *2);
		
		
		// Copy all elements from the old array to the new array
		for (int i = 0; i < size; i++){
			e[i + OFFSET] = eIn.getEdge(i);
		}
		
		// Sort the heap
		for (int i = size/2; i > 0; i--){
			percolateDown(i);
		}
		
		if (debug) prt ("Copied all elements from old array to the new array");
	}
	
	// Add an item to the heap
	public boolean add(Comparable eIn){
		
		if (debug) prt ("Adding " + eIn + " to the heap");
		
		// if the heap is full then return false
		if (isFull())
			return false;
		
		// Put the new element at the bottom of 
		// of the heap and move it to its correct
		// place in the array
		e[size + OFFSET] = eIn;
		percolateUp(size + OFFSET);
		size++;
		
		if (debug) prt ("Done");
		
		return true;
		
	}
	
	// remove the top element from the heap and return it
	public Comparable deleteMin(){
		
		// if the heap is empty then return -1
		if (isEmpty())
			return -1;
		
		// Will be returning the minimum value <temp> to 
		// the calling method. Replace the min value with the 
		// bottom value and move it to its correct place 
		// in the array and adjust the size of the heap
		Comparable temp = e[1];
		e[1] = e[size];
		percolateDown(1);
		size--;
		
		return temp;
	}
	
	// return the top element in the heap
	public Comparable poll(){
		return e[1];
	}
	
	// return true if the heap is empty
	public boolean isEmpty(){
		return (size == 0);
	}
	
	// return true if the heap is full
	public boolean isFull(){
		return size == e.length - OFFSET;
	}
	
	// return the heap size
	public int getSize(){
		return size;
	}
	
	// Move an element to its proper place in the array
	public void percolateUp(int start){
		
		if (debug) prt ("Running percolateUp +" + start);
		
		// Loop through all elements of the heap
		while (start > OFFSET){
			
			// Compare the contents of the array and swap
			// elements if necessary
			if (e[start].compareTo(e[start/2]) < 0){
				
				// An element was in the wrong place
				// so swap it
				Comparable temp = e[start/2];
				e[start/2] = e[start];
				e[start] = temp;
				
				// Continue to new element
				start = start / 2;	
			}
			// The element doesn't need to move so
			// exit the while loop
			else
				start = OFFSET;
		}
		if (debug) prt ("Done");
	}

	// Move an element to its proper place in the array
	public void percolateDown(int start){
		
		if (debug) prt ("Running percolateDown " + start);
		
		while (start <= size / 2){
			
			// Find the smallest child of the element
			int child;	
			if (size == 2 * start)
				child = 2 * start;
			else {
				if (e[2 * start].compareTo(e[(2 * start) + OFFSET]) < 0)
					child = 2 * start;
				else
					child =  2 * start + 1;
			}
	

			
			if (e[start].compareTo(e[child]) > 0){
				// An element was in the wrong place
				// so swap it
				Comparable temp = e[child];
				e[child] = e[start];
				e[start] = temp;
				
				// Now continue from the child of the element
				start = child;
			}
			else
				// The element is in the right spot in the array
				// so exit the while loop
				start = size;	
		}
		if (debug) prt ("Done");
		
	}
	
	// Method for quick and dirty test output
	public static void prt(String s){
			System.out.println("Heap: " + s);	
	}
	
}
